package graph;

/**
 *
 * @author wxh
 */
public class dfsTest {

	boolean found = false; // 全局变量或者类成员变量

	int v = 10;
	Graph graph = new Graph(v);

	public void dfs(int s, int t) {

		found = false;
		boolean[] visited = new boolean[v];
		int[] prev = new int[v];
		for (int i = 0; i < v; ++i) {
			prev[i] = -1;
		}
		recurDfs(s, t, visited, prev);
		print(prev, s, t);
	}

	private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
		if (found == true) return;
		visited[w] = true;
		if (w == t) {
			found = true;
			return;
		}
		for (int i = 0; i < graph.adj[w].size(); ++i) {
			int q = graph.adj[w].get(i);
			if (!visited[q]) {
				prev[q] = w;
				recurDfs(q, t, visited, prev);
			}
		}
	}

	private void print(int[] prev, int s, int t) { // 递归打印s->t的路径
		if (prev[t] != -1 && t != s) {
			print(prev, s, prev[t]);
		}
		System.out.print(t + " ");
	}

}